package listbyorder.access101_200.test143;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/12 8:34
 */
public class Solution1 {

    // 重排链表
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return;

        // 首先快慢指针将链表分割成为前后两个部分
        ListNode c1 = head;
        ListNode c2 = head.next;
        while (c2 != null && c2.next != null) {
            c1 = c1.next;
            c2 = c2.next.next;
        }
        ListNode second = c1.next;
        c1.next = null;

        // 将转化后的后半部分链表反转
        c1 = null;   // pre
        c2 = null;   // next
        while (second != null) {
            c2 = second.next;
            second.next = c1;
            c1 = second;
            second = c2;
        }

        // 将c1链表加入到c2(head)里面去
        c2 = head;
        while (c1 != null) {
            ListNode temp = c1;
            c1 = c1.next;
            ListNode next = c2.next;
            c2.next = temp;
            temp.next = next;
            c2 = next;
        }
    }
}
